/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

 //用栈记录中序遍历的结果
 //栈底到栈顶的数据要求严格递减，当后入的数据大于栈顶元素，就要将栈顶元素出栈
 //如果是一棵有效的搜索二叉树，那么遍历完后，栈内的元素个数一定是1
// class Solution {
// private:
//     void _isValidBST(TreeNode* root)
//     {
//         if (root == nullptr)
//             return;
        
//         _isValidBST(root->left);
//         if (!_st.empty() && root->val > _st.top())
//             _st.pop();
        
//         _st.push(root->val);
//         _isValidBST(root->right);
//     }
// public:
//     bool isValidBST(TreeNode* root) {
//         _isValidBST(root);

//         return _st.size() == 1;
//     }
// private:
//     stack<int> _st;
// };

//用一个变量标记遍历树时的前一个节点的值
class Solution {
private:
    bool _isValidBST(TreeNode* root, long long& prevVal)
    {
        if (root == nullptr)
            return true;
        
        bool left = _isValidBST(root->left, prevVal);
        bool cur = root->val > prevVal;
        prevVal = root->val;
        bool right = _isValidBST(root->right, prevVal);

        return left && cur && right;
    }
public:
    bool isValidBST(TreeNode* root) {
        long long prevVal = (long long)INT_MIN - 1;
        return _isValidBST(root, prevVal);
    }
};